package com.justnow.offer;


import netscape.security.UserTarget;
import sun.nio.cs.ext.MacHebrew;

import java.util.*;


/**
 * @author justnow
 * Created on 2020-09-22
 * Description
 */
public class Solution64 {

    public int lengthOfLongestSubstring(String s) {
        char[] array = s.toCharArray();
        LinkedList<Character> list = new LinkedList<>();
        int length = array.length;
        int max = 1;
        for (int i = 0; i < length; i++) {
            while (list.contains(array[i])) {
                list.removeFirst();
            }
            list.add(array[i]);
            max = Math.max(list.size(), max);
        }
        return max;
    }

    /**
     * 方法二，用hashmap来做，每次都移动右边的指针
     *
     * 1. left不动，right向后移动
     * 2. 当start遇到重复字符时，更新start，指向距离right且与right重复的位置的后一位，且记录最长的长度
     * 3. 用哈希表来判断的重复的字符，key为字符，value为下标的内容
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring02(String s) {
        int length = s.length();
        int left = 0, max = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int right = 0; right < length; ++right) {
            char temp = s.charAt(right);
            if (map.containsKey(temp)) {
                left = Math.max(map.get(temp) + 1, left); //更新距离right最近的非重复的子串,取left
            }
            max = Math.max(max, right - left + 1);
            map.put(temp, right);
        }
        return max;
    }

    public void lengthOfLongestSubstring03(String s) {
        int len = s.length();
        int start = 0;
        List<String> res = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0; end < len; end++) {
            char temp = s.charAt(end);
            if (map.containsKey(temp)) {
                res.add(s.substring(start, end));
                start = Math.max(map.get(temp) + 1, start);

            }
            map.put(temp, end);
        }
        Collections.sort(res, (x1, x2) -> {
            return x2.length() - x1.length();
        });
        System.out.println(res);
    }

    public static void main(String[] args) {
        Solution64 solution64 = new Solution64();
        solution64.lengthOfLongestSubstring03("abcabcbb");
    }
}
